class Solution(object):
    def partitionLabels(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        d1 = {}
        d2 = {}
        for i, c in enumerate(s):
            if c not in d1:
                d1[c] = i
            d2[c] = i
        st = []
        for key in d1:
            st.append([d1[key], d2[key]])
        st.sort()
        last = st[0]
        out = []
        for i in range(1, len(st)):
            if st[i][0] > last[1]:
                out.append(last[1] - last[0] + 1)
                last = st[i]
            else:
                last[1] = max(last[1], st[i][1])
        out.append(last[1] - last[0] + 1)
        return out


data = Solution()
s = "aaaaabbb"
print(data.partitionLabels(s))
